The interactive editing of video images is an important part of the field of video image processing. The editing and propagation of video image has been a focus of research in the field of computer vision. When an image or video is edited by a user, only a small number of the pixels are necessary to be edited. Other pixels can change accordingly as per the association relation established among various pixels and thus the effect of editing by user can be propagated to the whole image or video.
At present, some scientific researchers have carried out a large amount of studies on related techniques. As for the editing and propagation of image, Anat Levin et al. have put forward the framework regarding the method of editing and propagation of image for the first time in 2004. Extending this framework, Xiaobo An et al. raises a method of editing and propagation based on the similarity of all pixels in 2008. However, this method will consume too many memories and can't process the data of big image or video. Kun Xu et al. proposes a method of editing and propagation based on KD-tree in 2009 which establishes a relation between different pixels according to the distance of KD-tree between different pixels to realize the effect of propagation. Zeev Farbman et al. presents a method of editing and propagation based on diffusion distance (diffusion map) in 2010 which utilizes the diffusion distance to measure the similarity between different pixel points. Nevertheless, these methods can't process effectively the color transition region and the phenomena of color penetration and distortion often occur. Xiaowu Chen et al. raises a method of editing and propagation based on preserving local features and structures in 2012. This method can solve the problems of color penetration and distortion in color transition region. However, it still has great limitation in the consumption of memory and time. As a whole, in order to maintain the similarity among all the pixels during editing and propagation, a large amount of memory spaces have to be consumed. And the existing methods can't maintain a good sense of fidelity of result it the case of limited memory space and time.
With the advent and increase of high-resolution video images, the demand on processing technologies for such large-scale video images also starts to emerge. However, most of such existing techniques alike are based on a method of overall optimization and will inevitably led to excessive memory consumption and too long processing time. For example, a method of editing and propagation mentioned above raised by Xiaobo An, et al. of Dartmouth College of USA requires a memory space of about 23 GB during processing an image of 60 M pixels. It far exceeds the memory size of current ordinary computer and hence this technique is difficult to promote for application. Yong Li et al. of Tsinghua University of China proposes another method of editing and propagation of video images by which the consumption of memory can be improved though a color distortion is resulted. Thus, it is in an urgent need for a method of editing and propagation of video images which can maintain the fidelity of the result of video images with consuming very small memory.
In recent years, the sparse representation technique has already been applied in various fields such as the image analysis and understanding. Jianchao Yang et al. applies the sparse representation technique in image super-resolution and proposes a viewpoint to regard low-resolution image as the sparse sample of high-resolution image. In 2008, Julien Mairal et al. proposes a supervised learning framework based on multi-scale sparse representation to solve the problems of image denoising and padding. And Shenlong Wang et al. proposes a model of half-coupling dictionary learning in 2012 to solve the problem of image composition. In addition, the sparse representation technique is also widely applied in the fields of face recognition, image modeling and image classification, etc. However, no one has ever applied the sparse representation technique in the field of editing and propagation and focused it to solve the problem of memory consumption during processing high-resolution video images.